/*
 * @Author: 缄默
 * @Date: 2021-09-18 15:19:27
 * @LastEditors: 缄默
 * @LastEditTime: 2021-09-23 21:13:55
 */

//可见山峰对数量


#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Record {
    int value;
    int times;
    Record(int value) :value(value), times(1) { }
};

int getVisibleNum(vector<int>& arr);
int getInternalSum(int k);
int nextIndex(int i, int size);
 
int main() {

}

int getVisibleNum(vector<int>& arr) {
    if(arr.size() <= 2 || arr == nullptr) {
        return 0;
    }
    int size = arr.size();
    int maxIndex = 0;
    for(int i =0; i < size; i++) {
        maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
    }
    stack<Record> sta;
    //将最大点先放入堆栈
    sta.push(new Record(arr[maxIndex]));
    //从最大位置沿next方向寻找
    int index = nextIndex(maxIndex, size);
    int res = 0;
    while (index != maxIndex) {
        //当前数字要进栈判断会不会破坏第一维的数字从顶部到底以此变大的规律
        //如果破坏了就要弹出 并计算可见山峰的数量 按照小找大的规律计算
        while (arr[index] > sta.top().value) {
            //弹出的同时记录次数 记录该山峰形成的可见对
            int times = sta.pop().times;
            res += getInternalSum(times) + 2 * times;
        }
        //相等的话 次数加一
        if (arr[index] == sta.top().value) {
            sta.top().times++;
        }
        //不等的话 record放入堆栈
        else {
            sta.push(new Record(index));
        }
        index = nextIndex(index);
    }
    //弹出时 先判断是否大于二 大于2的话 每个可以和它前面的山形成一个 可以和第一个最高的山形成一个 就是两个 
    //times就记录这个山出现的次数成二 加上这个山内部形成的可见数量
    while (sta.size() > 2) {
        int times = sta.pop().times;
        res += getInternalSum(times) + 2 * times; 
    }
    //等于二时判断这个最高峰是否是一个 向前和向后看见的是否是一个
    if (sta.size() == 2) {
        int times = sta.pop().times;
        res += getInternalSum(times) + (sta.top().times == 1) ? times : 2 * times;
    }
    //最后的山加上自己内部形成的即可
    res += getInternalSum(sta.top().times);
    return res;

}

int getInternalSum(int k) {
    return k == 1 ? 0 : (k * (k - 1) / 2);
}

//寻找下一个索引
int nextIndex(int i, int size) {
    return i < (size - 1) ? (i + 1) : 0;
}